In a computing system, memory space can be allocated for use by a computing process. A “memory space” includes a number of positions in a memory of a computing device, each position corresponds to a unit of memory, such as, for example, a byte or word. A process uses items stored in the physical memory, for example, random access memory (RAM) that is installed in a computing device. In some computing systems, memory is de-allocated and made available for subsequent allocation once a process is finished using the memory.
In some systems, status information can be maintained for each portion of the memory space. Such status information can indicate whether the memory is allocated and, therefore, not available. Memory allocation is typically performed on a block basis, where memory blocks are allocated to a given process. A “memory block” is a contiguous portion of memory locations.
Management of the computing device's memory typically includes three operations: allocation, de-allocation, and consolidation. In the allocation phase, the computing device receives a request for a memory block and identifies one or more non-allocated blocks of memory to fill that request. The computing device can then allot the identified one or more blocks by marking the blocks as allocated and then communicating to the requesting process that the identified memory blocks are available for use. In the de-allocation phase, the computing device receives a communication indicating that a process is done with one or more previously allocated blocks of memory and then marks the one or more blocks as being available for subsequent allocation.
In allocating and de-allocating the memory, the computing device can fragment the memory into a number of blocks. If this process is continued unchecked, the memory can be divided into many small blocks of unused memory. In such instances, the computing device may have to satisfy allocation requests for memory by providing a large number of small blocks, even though a substantial portion of the memory space remains unused. This memory fragmentation can be inefficient in the use of the memory space and can result in lower computing efficiency.
To alleviate memory fragmentation, in the consolidation phase, the computing device can attempt to join one or several contiguous blocks of available memory to form a larger contiguous memory block. Thus, consolidation, also referred to as coalescing or defragmentation, can rearrange allocated fragments so that unused portions of the memory space are combined.